Masala #0748
Prefiks funksiya
Dasturlash musobaqasi bilan shug’ullanib yurgan barchaga Prefiks funksiya nima ekanligi ma’lum bo’lsa kerak. Agar bilmasangiz Prefiks funksiya haqida https://e-maxx.ru/algo/prefix_function havoladan o’rganib olishingiz mumkin.
Keling endi asosiy masalaga o’tamiz!
\(S\) to’plam \(m\) ta harfli alifbodan tuzilgan uzunligi \(n\) ga teng bo’lgan barcha satrlar to’plami.
\(F(s)\) funksiyasi \(\text{prefix\_function}(s)\) dan olingan to’plamning eng katta qiymati bo’lsin.
Sizning vazifangiz \(\sum_{s∈S}F(s)\) ni \(X\) ga bo’lgandagi qoldiqni hisoblashdan iborat.
Kirish faylining yagona satrida uchta butun son, \(n (1 \le n \le 22)\), \(m (1 \le m \le 10^9)\) va \(X (1 \le X \le 10^9)\) sonlari kiritiladi.
Chiqish faylida yagona butun son, \(\sum_{s∈S}F(s)\) ni \(X\) ga bo’lgandagi qoldiqni chop eting!
# | input.txt | output.txt |
---|---|---|
1 |
3 2 1000 |
8 |
- F(aaa) = 2
- F(aab) = 1
- F(aba) = 1
- F(abb) = 0
- F(baa) = 0
- F(bab) = 1
- F(bba) = 1
- F(bbb) = 2